func minInsertions(s string) int {
    var n = len(s)
    // dp[i][j] 表示对于字符串 s 的子串 s[i:j]（这里的下标从 0 开始，并且 s[i:j] 包含 s 中的第 i 和第 j 个字符），
    // 最少添加的字符数量，使得 s[i:j] 变为回文串
    var dp = make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    /*
        我们从外向内考虑 s[i:j]：

        如果 s[i] == s[j]，那么最外层已经形成了回文，我们只需要继续考虑 s[i+1:j-1]；

        如果 s[i] != s[j]，那么我们要么在 s[i:j] 的末尾添加字符 s[i]，要么在 s[i:j] 的开头添加字符 s[j]，
        才能使得最外层形成回文。如果我们选择前者，那么需要继续考虑 s[i+1:j]；如果我们选择后者，那么需要继续考虑 s[i:j-1]。

        因此我们可以得到如下的状态转移方程：

        dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)                     if s[i] != s[j]
        dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i + 1][j - 1])   if s[i] == s[j]
    */
    for len := 2; len <= n; len++ {
        for i := 0; i <= n - len; i++ {
            var j = i + len - 1
            dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
            if s[i] == s[j] {
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1])
            }
        }
    }

    return dp[0][n - 1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}